package com.demo.sort;

import cn.hutool.core.util.ArrayUtil;
import com.demo.sort.base.SortBase;

import java.util.Arrays;

/**
 * 归并排序(分治算法)
 * 该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。
 * 实现有两种:
 * 1. 自上而下的递归（所有递归的方法都可以用迭代重写，所以就有了第 2 种方法）；
 * 2. 自下而上的迭代；
 *
 * 过程:
 * 1. 通过二分确定最小单位   (左右比较合并成一个有序数组)
 * 2. 逐次合并(每次合并后为该最小单元中的有序列)
 * 3. 最后一层进行两个有序列的合并
 **/
public class MergeSort extends SortBase {

    public int[] init() {
        return new int[]{5, 6, 94, 52, 15, 3, 14, 5, 6, 1, 8, 923, 15};
    }

    @Override
    public void app() throws Exception {
        super.app();
        handler(this::sort);
    }

    public int[] sort(int[] init) {
        int[] ints = mergeSort(init);
        ArrayUtil.copy(ints, init, init.length);
        return init;
    }

    public int[] sort2(int[] arr) {
        int[] sortResult = new int[arr.length];
        sort(arr, 0, arr.length - 1, sortResult);
        return sortResult;
    }


    /**
     * 自上而下的递归
     */
    private int[] mergeSort(int[] init) {
        int len = init.length;
        if (len <= 1) return init;
        int mid = len / 2;
        int[] left = mergeSort(Arrays.copyOfRange(init, 0, mid));
        int[] right = mergeSort(Arrays.copyOfRange(init, mid, len));
        return merge(left, right);
    }

    private int[] merge(int[] left, int[] right) {
        int lLen = left.length, rLen = right.length;
        int[] result = new int[lLen + rLen];
        int i = 0, leftIndex = 0, rightIndex = 0;
        while (leftIndex < lLen && rightIndex < rLen) {
            result[i++] = left[leftIndex] > right[rightIndex] ? right[rightIndex++] : left[leftIndex++];
        }
        boolean leftEndFlag = leftIndex == lLen;
        System.arraycopy(leftEndFlag ? right : left, leftEndFlag ? rightIndex : leftIndex,
                result, rightIndex + leftIndex,
                leftEndFlag ? rLen - rightIndex : lLen - leftIndex);
        return result;
    }

    private void sort(int[] arr, int left, int right, int[] temp) {
        if (left < right) {
            int mid = (left + right) / 2;
            sort(arr, left, mid, temp);
            sort(arr, mid + 1, right, temp);
            merge(arr, left, mid, right, temp);
        }
    }

    private void merge(int[] arr, int left, int mid, int right, int[] temp) {
        int i = left;
        int j = mid + 1;
        int t = 0;
        while (i <= mid && j <= right) {
            if (arr[i] <= arr[j]) {
                temp[t++] = arr[i++];
            } else {
                temp[t++] = arr[j++];
            }
        }
        while (i <= mid) {//将左边剩余元素填充进temp中
            temp[t++] = arr[i++];
        }
        while (j <= right) {//将右序列剩余元素填充进temp中
            temp[t++] = arr[j++];
        }
        t = 0;
        //将temp中的元素全部拷贝到原数组中
        while (left <= right) {
            arr[left++] = temp[t++];
        }
    }
}